package find.the.first.nonrepeating.character;

import java.util.HashMap;

/**
 * @Time 2019/12/22
 * @author 王光浩
 * @Need 给定一个字符串，找到该字符串中第一个不重复的字符，并将其下标返回，如果不存在则返回-1。
 * @Thinking 使用HashMap。key值为字符串中字符，value为对应字符的下标。
 *           解决思路：创建一个数组，长度等于字符串字符的长度，然后我们遍历字符串，将数据不断加入到HashMap
 *                    中，如果当前待加入的字符在HashMap中已经存在则将当前字符对于数组元素值置位-1，并且将
 *                    HashMap中字符所对应下标在数组元素值加一，最后遍历数组找到第一个值为0的数据就行。
 *                    （这里0表示元素只存在一次、-1表示元素存在多次）
 *           复杂度分析：时间复杂度O（n），空间复杂度O（n）（为什么在实际中运行时间这么长因为当我们需要扩展HashMap）
 */
public class MyMethodOne {
    public int firstUniqChar(String s) {
        int len=s.length();
        int[] result=new int[len];
        HashMap<Character,Integer> hashMap=new HashMap<Character,Integer>();
        for(int i=0;i<len;i++) {
        	//如果当前字符在HashMap中存在表示在该字符之前有一个与与该字符相同的字符存在
        	if(hashMap.containsKey(s.charAt(i))) {
        		result[i]=-1;       //在字符串中i位置为字符已经存在
        		result[hashMap.get(s.charAt(i))]=-1; 
        		continue;
        	}
        	hashMap.put(s.charAt(i), i);
        }
        //获取第一个不重复的字符
        for(int i=0;i<len;i++) {
        	if(result[i]==0)
        		return i;
        }
        //在该字符串中不存在这样的字符
        return -1;
    }
}
